Scheduling elevators in a large building is a well-known hard industrial problem. The problem is characterized by very large state spaces and significant uncertainty, see Barney, “Elevator Traffic Handbook,” Spon Press, London, 2003. Typically, a passenger requests elevator service by pressing a call button. This causes the elevator scheduler to assign an elevator car to service the passenger.
The earliest elevator schedulers used the principle of collective group control. In this heuristic, the nearest car, in its current direction of travel, is assigned to service the passenger, see Strakosch, “Vertical transportation: elevators and escalators,” John Wiley & Sons, Inc., 1998. Such scheduling is sub-optimal and unpredictable. For this reason, collective control is unacceptable when passengers expect to be notified about which car will pick them up, immediately after the call is made.
Another heuristic minimizes a remaining response time (RRT) for each passenger. The RRT defines the time it takes to pick up each passenger as prescribed by the current schedule, see U.S. Pat. No. 5,146,053, “Elevator dispatching based on remaining response time,” issued to Powell et al., on Sep. 8, 1992. That heuristic focuses only on minimization the waiting time of passengers, and ignores altogether the effect of the current assignment on the waiting times of future passengers.
Within RRT-based minimization, a further distinction can be made between those methods that ignore the uncertainty associated with the desired destination floors of passengers, see Bao, “Elevator dispatchers for down-peak traffic,” Technical Report, University of Massachusetts, Department of Electrical and Computer Engineering, Amherst, Mass., 1994, and those that properly determine the expected RRT of each passenger with respect to destinations, see Nikovski et al., “Decision-theoretic group elevator scheduling,” 13th International Conference on Automated Planning and Scheduling, Trento, Italy, June 2003, and U.S. patent application Ser. No. 10/161,304 “Method and System for Dynamic Programming of Elevators for Optimal Group Elevator Control,” filed by Brand et al. on Jun. 3, 2002, incorporated herein by reference.
However, the uncertainty associated with future passengers is entirely new matter for at least two reasons. Accounting properly for the effect of the current decision on the waiting times of all future passengers is an extremely complicated problem, First, the uncertainty associated with future passengers is much higher because the arrival time, the arrival floor, and the destination floor are all unknown. Second, the current decision potentially influences the waiting times of passengers arbitrarily far into the future, which makes the theoretical optimization horizon of the problem infinite.
In spite of the computational difficulties, ignoring future passengers often leads to sub-optimal scheduling results. The current assignment affects the future movement of the cars, and influences their ability to serve future calls in the minimal amount of time.
One particular situation that exemplifies the importance of future passengers is peak traffic. During down-peak traffic periods, for example, at or near the end of the workday, most future passengers select the main floor as their destination. Because these future passengers are most likely distributed over upper floors, scheduling for down-peak traffic is a very hard problem.
During up-peak traffic periods, most future passengers arrive at the main floor and request service to upper floors. Typically, the up-peak period is much shorter, busier and concentrated than the down-peak period. Therefore, up-peak throughput is usually the limiting factor that determines whether an elevator system is adequate for a building. Therefore, optimizing the scheduling process for up-peak traffic is important.
Consider the following scenario. A call is made at some upper floor. A single car is parked at the main floor, and the scheduler decides to serve the call with that car, based only on the projected waiting times of passengers. If the car at the main floor car is dispatched to serve the call, the main floor remains uncovered and future passengers will have to wait much longer than if the car had stayed. This shortsighted decision, commonly seen in conventional schedulers has an especially severe impact during up-peak traffic, because the main floor quickly fills with many waiting passengers, while the car services the lone passenger above.
Several elevator scheduling methods are known for considering future passengers, with varying success. Some schedulers use fuzzy rules to identify situations similar to the one discussed above and make decisions that are more sensitive to future events, see Ujihara et al., “The revolutionary AI-2000 elevator group-control system and the new intelligent option series,” Mitsubishi Electric Advance, 45:5–8, 1988. However, that method has major disadvantages. First, the rules need to be coded manually. Therefore, the system is only as good as the ‘expert’. Second the interpretation of fuzzy-rule inferences between the rules often behaves erratically, particularly when there is no applicable rule for some specific situation. Thus, the elevators often operate in an unintended and erratic manner.
Another method recognizes that group elevator scheduling is a sequential decision making problem. That method uses the Q-learning algorithm to asynchronously update all future states of the elevator system, see Crites et al., “Elevator group control using multiple reinforcement learning agents,” Machine Learning, 33:235, 1998. They dealt with the huge state space of the system by means of a neural network, which approximated the costs of all future states. Their approach shows significant promise. However, its computational demands render it completely impractical for commercial systems. It takes about 60,000 hours of simulated elevator operation for the method to converge for a single traffic profile, and the resulting reduction of waiting time with respect to other much faster algorithms was only 2.65%, which does not justify its computational costs.
The prior art methods are either labor-intensive or computationally expensive or both. Therefore, there is a need for a method that optimally schedules elevator cars, while taking future passengers into consideration, particularly for up-peak traffic intervals.
Summary of the Invention